package leetcode.hot100;

import leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

@SuppressWarnings("all")
public class _94_二叉树的中序遍历 {

    // 通过迭代算法完成
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) return resultList;
        // 遍历顺序：左-根-右
        // 从根结点开始出发，先遍历左子树，如果左子树为空，那么再遍历根结点，接着遍历右子树
        Stack<TreeNode> stack = new Stack<>();
        // 遍历指针，不破坏原本的树结构
        TreeNode node = root;
        // node不为空说明还在对当前结点进行中序遍历
        // node为空说明当前结点左右子树遍历结束，需要弹栈对node的父结点继续未完成的中序遍历
        while (node != null || !stack.isEmpty()) {
            // 一直往左压栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            // 最左的一个结点即是遍历的起始结点
            node = stack.pop();
            // 保存根
            resultList.add(node.val);
            // 往右走一步，再继续循坏
            // 根 ---> 右
            node = node.right;
        }
        return resultList;
    }
}
